package com.fr.lintcode;

/**
*作者：furong
*日期：2016年12月28日
*时间：下午4:00:36
*/
public class Q141 {
    public int sqrt(int x) {
        StringBuffer sb = new StringBuffer();
        String k = String.valueOf(x);
        int lenth = k.length();
        int q = 0;
        long left = 0;
        if (lenth % 2 == 0) {
            left = Integer.parseInt(k.substring(0, 2));
            q = 2;
        } else {
            left = Integer.parseInt(k.substring(0, 1));
            q = 1;
        }
        int t;
        for (t = 1; t < 10; t++) {
            if (t * t > left) {
                break;
            }
        }
        t = t - 1;
        left = left - t * t;
        sb.append(t);
        while (q < k.length()) {
            left = square1(sb, left, q, k);
            q += 2;
        }
        return Integer.parseInt(sb.toString());
    }

    private long square1(StringBuffer sb, long left, int q, String k) {
        int x = Integer.parseInt(sb.toString().replace(".", ""));
        left = left * 100 + getValue(k, q);
        int t;
        for (t = 1; t < 10; t++) {
            if ((x * 20 + t) * t > left) {
                break;
            }
        }
        t = t - 1;
        left = left - ((x * 20 + t) * t);
        if (q == k.length()) {
            sb.append(".");
        }
        sb.append(t);
        return left;
    }

    private int getValue(String k, int q) {
        if (q >= k.length()) {
            return 0;
        }
        return Integer.parseInt(k.substring(q, q + 2));
    }
}
